package leetcode.Hot100;

import leetcode.TreeNode;
import leetcode.TreeNodeUtil;

/**
 * @author Cheng Jun
 * Description: 路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。
 * 同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 * <p>
 * 路径和 是路径中各节点值的总和。
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 * <p>
 * 树中节点数目范围是 [1, 3 * 104]
 * -1000 <= Node.val <= 1000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/19 15:49
 * 二刷 面试题
 */
public class maxPathSum {


    int max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        // TreeNodeUtil 构造树有问题
        TreeNodeUtil.getBT(new Object[]{5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1});
        System.out.println(new maxPathSum().maxPathSum(TreeNodeUtil.getBT(new Object[]{0, 1, 1})));
    }

    //    -10
    //  9      20
    //       15  7
    // 答案肯定是 以树中的某个节点 为根节点的子树
    // max = root.val + root.left的max + root.right的max
    public int maxPathSum(TreeNode root) {
        maxPathSumRec(root);
        return max;
    }

    // 这道题的经典之处在于，递归的过程中，你只能选择当前节点的左子树或右子树 与节点值相加，也就是选择半边树。
    // 但是，题目的求解目标是，当前节点的节点值 + 左子树的最大值 + 右子树的最大值
    // 而且运用到了贪心算法，就是当前如果 nodeMax 小于0 就舍弃。
    private int maxPathSumRec(TreeNode root) {
        if (root == null) return 0;
        // 节点的最大路径和，需要看 左子树提供的leftMax 和 右子树提供的rightMax
        int leftMax = maxPathSumRec(root.left);
        int rightMax = maxPathSumRec(root.right);
        int nodeMax = root.val;
        // 需要看提供的 leftMax，rightMax 谁大
        if (leftMax > rightMax) {
            nodeMax += leftMax;
            // 每次计算出一个nodeMax 都和 当前的max做一次比较
            // 注意这里还要加上 rightMax 才是节点的 maxPathSum
            this.max = Math.max(this.max, nodeMax + rightMax);
        }
        if (rightMax >= leftMax) {
            nodeMax += rightMax;
            this.max = Math.max(this.max, nodeMax + leftMax);
        }
        // 如果 nodeMax 小于0 就舍弃
        return nodeMax >= 0 ? nodeMax : 0;
    }
}
